Krichevsky–Trofimov estimator
In information theory, given an unknown stationary source π with alphabet A, and a sample w from π, the Krichevsky–Trofimov (KT) estimator produces an estimate πi(w) of the probabilities of each symbol i ∈ A. This estimator is optimal in the sense that it minimizes the worst-case regret.
For a binary alphabet, and a string w with m zeroes and n ones, the KT estimator can be defined recursively[1] as:
![\begin{array}{lcl}
P(0, 0) & = & 1, \\ [6pt]
P(m, n%2B1) & = & P(m,n)\dfrac{n %2B 1/2}{m %2B n %2B 1}, \\ [12pt]
P(m%2B1, n) & = & P(m,n)\dfrac{m %2B 1/2}{m %2B n %2B 1}.
\end{array}](/2012-wikipedia_en_all_nopic_01_2012/I/d294803c1246f2546a79a788d5689705.png)
See also
References
- ^ Krichevsky, R.E. and Trofimov V.K. (1981), 'The Performance of Universal Encoding', IEEE Trans. Information Theory, Vol. IT-27, No. 2, pp. 199–207